Internet Archive's in-browser bookreader "theater" requires JavaScript to be enabled. It appears your browser does not have it turned on. Please see your browser settings for this feature.

Classical simulability and the significance of modular exponentiation in Shor's algorithm

by: Nadav Yoran; Anthony J. Short

Publication date: 2007-06-06

Collection: arxiv; additional_collections; journals

Language: English

We show that a classical algorithm efficiently simulating the modular exponentiation circuit, for certain product state input and with measurements in a general product state basis at the output, can efficiently simulate Shor's factoring algorithm. This is done by using the notion of the semi-classical Fourier transform due to Griffith and Niu, and further discussed in the context of Shor's algorithm by Browne.